package com.lw.leetcode.binary.a;

/**
 * binary
 * 69. x 的平方根
 * 剑指 Offer II 072. 求平方根
 *
 * @Author liw
 * @Date 2021/4/16 10:53
 * @Version 1.0
 */
public class MySqrt {

    public static void main(String[] args) {

//        System.out.println(Integer.MAX_VALUE);
//
//        int i = 2147395599;
//        System.out.println(i * i);
//
//        System.out.println(Math.sqrt(Integer.MAX_VALUE));


        for (int i = 100; i <= 100; i++) {

            int n = new MySqrt().mySqrt(2147395599);
            System.out.println(i + " :  " + n);
        }
    }

    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x < 4) {
            return 1;
        }
        // 怕越界，先写死
        if (x >= 2147395600) {
            return 46340;
        }
        int st = 0;
        int end = x;
        int m = st + ((end - st) >> 1);
        // 怕越界，先写死
        if (m >= 46340) {
            m = 46340;
        }
        while (st <= end) {
            int s = m * m;
            if (s <= x && (m + 1) * (m + 1) > x) {
                return m;
            }
            if (s > x) {
                end = m - 1;
            } else {
                st = m + 1;
            }
            m = st + ((end - st) >> 1);
        }
        return 0;
    }
}
